package com.datastructure.sparse;

import java.util.Random;

public class SparseArray {
    public static void main(String[] args) {
        SparseArray mSparseArr = new SparseArray();

        //创建原始二维数组
        int[][] originArr = mSparseArr.generateOriginArr();
        mSparseArr.printArr(originArr,"原始数组");

        //生成稀疏数组
        int[][] sparseArr = mSparseArr.convertToSparseArr(originArr);
        mSparseArr.printArr(sparseArr,"稀疏数组");

        //将稀疏数组转换成普通二维数组
        int [][] originArrFromSparse = mSparseArr.convertToOriginArr(sparseArr);
        mSparseArr.printArr(originArrFromSparse,"从稀疏数组还原后的数组");
    }

    /**
     * 生成原始二维数组 10*10
     * 随机选择三个位置，产生非 0 有效数字
     */
    public int[][] generateOriginArr() {
        int[][] originArr = new int[10][10];
        //to generate 3 non-zero number
        Random random = new Random();
        for(int i=0;i<3;++i) {
            int row = random.nextInt(9);
            int col = random.nextInt(9);
            originArr[row][col] = 1;
        }
        return  originArr;
    }

    //打印数组
    public void printArr(int[][] array,String type) {
        System.out.println(type + ":");
        for(int[] row:array) {
            for(int num:row) {
                System.out.print(num + "\t");
            }
            System.out.println();
        }
    }

    //将二维原始数组转换为稀疏数组
    public int[][] convertToSparseArr (int[][] originArray) {
        int rowLen= originArray.length;
        int colLen = originArray[0].length;
        //有效元素个数
        int numOfValidElement = countValidElement(originArray);

        int[][] sparerArray = new int[numOfValidElement+1][3];
        //稀疏数组的第一行
        sparerArray[0][0] = rowLen;
        sparerArray[0][1] = colLen;
        sparerArray[0][2] = numOfValidElement;
        //生成稀疏数组的元素
        int count = 0; //第几(count)个有效元素
        for (int i=0;i<rowLen;++i) {
            for (int j=0;j<colLen;++j) {
                if (originArray[i][j] !=0) {
                    ++count;
                    sparerArray[count][0] = i;
                    sparerArray[count][1] = j;
                    sparerArray[count][2] = originArray[i][j];
                }
            }
        }
        return  sparerArray;
    }

    //统计原始数组中有效元素（非0）的个数，尽管我们知道是 3
    private int countValidElement(int[][] originArray) {
        int count = 0;
        for(int[] row:originArray) {
            for (int num : row) {
                if (num != 0) {
                    ++count;
                };
            }
        }
        System.out.println("有效元素个数为: " + count);
        return count;
    }

    //将稀疏数组转换为原始二维数组
    public int[][] convertToOriginArr(int[][] sparseArray) {
        //获取原始数组行列信息
        int rowLen = sparseArray[0][0];
        int colLen = sparseArray[0][1];
        int[][] originArray = new int[rowLen][colLen];
        for(int i=1;i<sparseArray.length;++i) {
            int[] line = sparseArray[i];
            originArray[line[0]][line[1]] = line[2];
        }
        return originArray;
    }
}